package leecode.array.其他;

/**
 * https://leetcode.cn/problems/sort-colors/
 */
public class SortColors {

    /**
     * 比较简单的解法：直接统计0,1,2的个数，然后数组重新填充下即可。时间O(n)，2趟遍历
     * 面试的时候 就用第一种思路比较好
     *
     * 下面的解法一趟遍历
     */

    public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return;
        }
        int i = 0;
        int j = nums.length - 1;
        for (int p = 0; p < nums.length; p++) {
            if (nums[p] == 1) {
                continue;
            } else if (nums[p] == 0) {
                swap(nums, p, i);
                i++;

                // p <= j  这个条件是防止 后面的2又被调到前面了
            } else if (nums[p] == 2 && p <= j) {
                swap(nums, p, j);
                j--;
                // 注意 2 挪完如果换出来的不是 1，那么指针要回退，因为 0 和 2 都是需要再次移动的
                if (nums[p] != 1) {
                    p--;
                }
            }
        }
    }

    public void sortColors2(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return;
        }
        int count0 = 0;
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count0++;
            } else if (nums[i] == 1) {
                count1++;
            } else if (nums[i] == 2) {
                count2++;
            }
        }
        int p = 0;
        while (p < count0) {
            nums[p++] = 0;
        }
        while (p < count1 + count0) {
            nums[p++] = 1;
        }
        while (p < count2 + count1 + count0) {
            nums[p++] = 2;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
